package dataStructure.Recursion;

/**
 * @author lhn
 * @date 2024-08-28 15:22
 * 迷宫问题
 */

public class Labyrinth {
    public static void main(String[] args) {
        //创建二维数组，模拟迷宫
        int[][] map = new int[8][7];

        //0 表示路
        //1 表示墙
        //2 表示走的路
        for (int i = 0; i < 7; i++) {
            map[0][i] = 1;
            map[7][i] = 1;
        }
        for (int i = 0; i < 8; i++) {
            map[i][0] = 1;
            map[i][6] = 1;
        }

        map[3][1] = 1;
        map[3][2] = 1;

        //打印地图
        System.out.println("地图如下：");
        printMap(map);

        System.out.println(
                "从(1,1)出发，寻找路径："
        );

//        System.out.println("策略：↓→↑←");
//        findWay(map, 1, 1);
//        printMap(map);

        System.out.println("策略：↑→↓←");
        findWay_2(map, 1, 1, 0);
        printMap(map);
    }

    public static void printMap(int[][] map) {
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
    }

    /**
    * 使用递归找路
    * 1.从地图上的(1,1)出发，一直向右下角走，直到右下角为1，表示走不通
    * 2.如果找到右下角(6,5)，返回true
    * 3.当map[i][j]=0时，表示该点没有走过，可以走
    * 4.map[i][j]=2表示该点通路
    * 5.map[i][j]=3表示该点是死路
    * 6.以走，先走，然后判断右，下，左，右是否有路，如果有路就继续走，直到走不通，返回false
    * @author lihaonan
    * @date 2024/8/28 15:28
     * @param map 传入地图
     * @param i 出发位置的坐标x
     * @param j 出发位置的坐标y
     * @return boolean
     *
    */
    public static boolean findWay(int[][] map, int i, int j) {
        if (map[6][5] == 2) {
            //到达终点
            return true;
        } else {
            if (map[i][j] == 0) {
                //当前点没有走过
                map[i][j] = 2;  //假定该点是通路
                if (findWay(map, i + 1, j)) {
                    //向下走
                    return true;
                } else if (findWay(map, i, j + 1)) {
                    //向右走
                    return true;
                } else if (findWay(map, i - 1, j)) {
                    //向上走
                    return true;
                } else if (findWay(map, i, j - 1)) {
                    //向左走
                    return true;
                } else {
                    map[i][j] = 3;  //该点是死路
                    return false;
                }
            } else {
                //该点已经走过，或者该点是死路
                return false;
            }
        }
    }

    /**
    * 策略：上右下左
    * @author lihaonan
    * @date 2024/8/28 16:00
     * @param map
     * @param i
     * @param j
     * @return boolean
    */
    public static boolean findWay_2(int[][] map, int i, int j, int stepCount) {
        if (map[6][5] == 2) {
            //到达终点
            System.out.println("步数：" + stepCount);
            return true;
        } else {
            if (map[i][j] == 0) {
                //当前点没有走过
                map[i][j] = 2;  //假定该点是通路
                stepCount ++;
                if (findWay_2(map, i - 1, j, stepCount)) {
                    //向上走
                    return true;
                } else if (findWay_2(map, i, j + 1, stepCount)) {
                    //向右走
                    return true;
                } else if (findWay_2(map, i + 1, j, stepCount)) {
                    //向下走
                    return true;
                } else if (findWay_2(map, i, j - 1, stepCount)) {
                    //向左走
                    return true;
                } else {
                    map[i][j] = 3;  //该点是死路
                    stepCount --;
                    return false;
                }
            } else {
                //该点已经走过，或者该点是死路
                return false;
            }
        }
    }

}
